# sgt == segment tree
# 单点更新，区间查询
# 区间更新，单点查询
# 区间更新，区间查询

snippet sgt_one "线段树，单点更新" b

endsnippet

snippet sgt_range "线段树，区间更新" b
namespace SGT {
    /* =====  线段树区间更新--lazy [区间加,区间求和] ====*/
    /* 区间加,区间求和 的线段树 */
    struct node {
        int v;
        int flag=-1;
    }t[maxn];

    inline void _merge(node &a,node &b,node &c){ //合并
        a.v = b.v+c.v;
    }

    inline int lc(int o ){ return o<<1;}
    inline int rc(int o ){ return (o<<1)|1;}
    /* 更新父亲 */
    inline void pushup(int o){
        _merge( t[o] , t[lc(o)] , t[rc(o)]);
    }

    /* 向下更新标记 */
    void pushdown(int o,int m){
        if(t[o].flag !=-1 ){
            t[lc(o)].flag += t[o].flag;   //[改]
            t[rc(o)].flag += t[o].flag;   //[改]
            //[改]
            t[lc(o)].v += t[o].flag*(m-(m>>1));  /* 左孩子的值改变,上面有标记 */
            //[改]
            t[rc(o)].v += t[o].flag*(m>>1);  /* 右孩子的值改变,上面有标记 */
            t[o].flag = 0;
        }
    }
    /* 区间更新 -- lazy */
    void update(int l1,int r1,int c,int l,int r,int o){
        if(l1 <=l && r<=r1){
            t[o].flag += c; //我们到达一个点 [改]
            t[o].v += (r-l+1)*c; //[改]
            return ;
        }
        pushdown(o,(r-l+1)); //查看当前点对应标记树是不是有标记,如果有就往下压
        int m = (l+r)>>1;
        if( l1 <= m) update(l1,r1,c,l,m,lc(o));
        if( r1 > m) update(l1,r1,c,m+1,r,rc(o));
        pushup(o);
    }

    /* 区间查询 */
    int query(int l1,int r1,int l,int r,int o){
        if(l1<=l && r <= r1){//包含
            return t[o].v;
        }

        //路过
        pushdown(o,(r-l+1));
        int ret = 0;
        int m = (l+r)>>1;
        if(l1 <= m) ret+= query(l1,r1,l,m,lc(o));
        if(r1 > m ) ret+= query(l1,r1,m+1,r,rc(o));
        return ret;
    }

    /* 建立线段树 */
    void build(int l,int r,int o){
        if( l==r){
            scanf("%d",&t[o].v);
            return ;
        }
        int m = (l+r)>>1;
        build(l,m,lc(o));
        build(m+1,r,rc(o));
        pushup(o);
    }
#ifdef DEBUG
    void _dfs_print(ll l,ll r,ll o,FILE *dot){
        if( o >>1) fprintf(dot,"%d--%d;\n",o>>1,o);
        fprintf(dot,"%d[label=\"%d\"]\n",o,t[o].v);
        if( l == r) return;
        ll m = (l+r)>>1;
        _dfs_print(l,m,lc(o),dot);
        _dfs_print(m+1,r,rc(o),dot);
    }
    void sgt_2_dot(ll size,string name){
        FILE *dot = fopen(name.c_str(),"w");
        fprintf(dot,"graph g {\n node[shape=circle fixedsize=true style=filled fillcolor=white colorscheme=accent8 ];\n");
        _dfs_print(1,size,1,dot);
        fprintf(dot,"}");
    }
#endif
}
/* ====== 线段树区间更新--lazy-- END ====*/
endsnippet

snippet dsgt "动态开点线段树" b
TODO
endsnippet

snippet vsgt "权值线段树" b
TODO
endsnippet
